/**
 * 链表节点定义
 */
class ListNode {
    val: number
    next: ListNode | null
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val === undefined ? 0 : val)
        this.next = (next === undefined ? null : next)
    }
}
/**
 * K 个一组翻转链表
 * 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
 * 
 * 算法思路：
 * 1. 使用虚拟头节点简化边界处理
 * 2. 每次找到一组 k 个节点
 * 3. 将这一组节点从链表中分离出来
 * 4. 翻转这一组节点
 * 5. 将翻转后的组重新连接回链表
 * 
 * 时间复杂度：O(n)，其中 n 是链表的长度
 * 空间复杂度：O(1)，只使用了常数额外空间
 */
function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
    // 空链表直接返回
    if (!head) {
        return null
    }
    
    // 创建虚拟头节点，简化边界处理
    const dummy = new ListNode(0, head)
    // prevGroupTail: 上一组翻转后的尾节点（翻转前是头节点）
    let prevGroupTail: ListNode | null = dummy
    // groupTail: 当前组的尾节点
    let groupTail: ListNode | null = dummy
    
    while (true) {
        // 找到当前组的尾节点（向前移动 k 步）
        for (let i = 0; i < k && groupTail; i++) {
            groupTail = groupTail.next
        }
        
        // 如果不足 k 个节点，说明已经处理完所有完整的组
        if (!groupTail) {
            break
        }
        
        // 记录当前组的头节点和下一组的头节点
        const groupHead: ListNode | null = prevGroupTail!.next
        const nextGroupHead = groupTail.next
        
        // 将当前组从链表中分离出来（断开连接）
        groupTail.next = null
        prevGroupTail!.next = null
        
        // 翻转当前组
        reverseList(groupHead)
        
        // 将翻转后的组重新连接回链表
        // 翻转后，原来的 groupTail 变成了新的 groupHead，原来的 groupHead 变成了新的 groupTail
        prevGroupTail!.next = groupTail  // 连接上一组的尾节点到当前组翻转后的头节点
        groupHead!.next = nextGroupHead  // 连接当前组翻转后的尾节点到下一组的头节点
        
        // 更新指针，为下一组做准备
        prevGroupTail = groupHead  // 当前组翻转后的尾节点成为下一组的 prevGroupTail
        groupTail = prevGroupTail  // 从新的 prevGroupTail 开始寻找下一组
    }
    
    return dummy.next
};
/**
 * 翻转链表
 * 使用迭代方法翻转链表
 * 
 * @param l1 要翻转的链表的头节点
 * @returns 翻转后的链表的头节点
 */
function reverseList(l1) {
    let prev = null  // 前一个节点
    let curr = l1    // 当前节点
    
    while (curr) {
        // 保存下一个节点
        const next = curr.next
        // 反转当前节点的指针
        curr.next = prev
        // 移动指针
        prev = curr
        curr = next
    }
    
    // prev 指向翻转后的头节点
    return prev
}